package backtrackAlgorithm;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

/**
 * @author kunkun
 * @className LeetCode_22
 * @Description 括号生成
 * @date 2025/3/20 13:24
 */
public class LeetCode_22 {

    public List<String> generateParenthesis(int n) {
        ArrayList<String> list = new ArrayList<>();
        solution_1(n,0,0,list,"",0);
        return list;
    }

    @Test
    public void test(){
        for (String s : generateParenthesis(1)) {
            System.out.print(s+" ");

        }
    }

    private void solution_1(int n, int num1, int num2, ArrayList<String> list, String str,int index) {
        //1. 判断
        if (num1<num2){
            return;
        }
        if (num1>n || num2>n){
            return;
        }
        if (num1==num2 && num1==n){
            list.add(str);
            return;
        }
        //2. 循环
//        for (int i = index; i < n*2; i++) {
        str+="(";
        solution_1(n,num1+1,num2,list,str,index+1);
        str=str.substring(0,str.length()-1);
        str+=")";
        solution_1(n,num1,num2+1,list,str,index+1);
        str=str.substring(0,str.length()-1);
//        }

    }

}
